package Array_and_String;
/*
最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串""。
示例 1：
输入：strs = ["flower","flow","flight"]
输出："fl"
示例 2：
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/array-and-string/ceda1/
 */

public class _31最长公共前缀 {
    public static void main(String[] args) {

        String[] strs = {"dog","racecar","car"};

        System.out.println(longestCommonPrefix1(strs));


    }

    //方法一: 横向扫描
    public static String longestCommonPrefix1(String[] strs) {

        if (strs == null || strs.length == 0)
        {
            return "";
        }

        //遍历数组，两两比较最长公共前缀，最终答案数组若为0，则返回""
        String s = strs[0];

        for (int i = 1; i < strs.length; i++) {
            s = compareStr(s, strs[i]);
        }
        if (s.length() == 0 || s == null) {
            return "";
        }
        return s;
    }

    public static String compareStr(String prefixstr, String str) {
        int i = 0;
        for (i = 0; i < Math.min(prefixstr.length(),str.length()); i++) {
            if (str.charAt(i) != prefixstr.charAt(i)) {
                return str.substring(0, i);
            }
        }
        return str.substring(0, i);
    }


}
